1. The Field of the Invention
The present invention relates to filteringy events, data, or other instances of classes organized in an object-oriented schema. In particular, the present invention relates to constructing and using filtering trees that can be traversed to determine whether an event, data, or another instance satisfies the terms of a query.
2. The Prior State of the Art
Query language has been used for years to define the parameters used to select and retrieve data stored in relational databases. There are many methods and associated algorithms that have been developed to convert a query-based retrieval definition to computer-executable instructions that identify particular data entries in a relational database that satisfy the query-based retrieval definition. Abstract syntax trees are tools that have been developed for graphically representing the logical operations and order of operations that are executed when processing a query-based definition. Abstract syntax trees are one type of filtering tree, and represent procedures by which data or other types of information can be filtered according to logical operations specified, for example, by query-based definitions.
FIGS. 1A-1C illustrate abstract syntax trees associated with conventional methods for processing query-based definitions. While conventional methods for processing query-based definitions have proven adequate in some situations, they often become inefficient when applied to large numbers of separate definitions, as will be more fully described below.
The abstract syntax trees of FIGS. 1A-1C represent operations executed when processing, respectively, the logical expressions of the following three query-based definitions: ##EQU1##
In the foregoing query-based definitions, the notation &lt;object&gt; represents any selected object-oriented data class. Turning to FIG. 1A, processing the logical expression of query Q1 is conducted by comparing a data entry in the relational database against the information represented by the nodes of abstract syntax tree 10. Suppose that a first data entry contained in the relational database has x, y and z parameters with the following values: ##EQU2##
First, the "and" clause represented by node 11 indicates that both branches that depend therefrom must generate true values for the associated query-based definition to be satisfied. The process of comparing data entry D1 against query Q1 proceeds to node 12 which indicates that the operation to be conducted will involve a "greater than" comparison. Next, nodes 13 and 14 specify that the value of the x parameter is to be compared to the number 2. Because the x parameter of data entry D1 has a value of 4, the first branch consisting of nodes 12-14 generates a true value.
Next, the process steps back to node 12 and proceeds to the second branch, which consists of nodes 15-17. Node 15 indicates that a "less than" operation will be conducted on the second branch. According to nodes 16 and 17, the y parameter of the data entry is to be compared to the number 3. Since the y parameter has a value of 5, the second branch yields a false value. The process steps back to node 10 and, since the second branch has a false value, data entry D1 does not satisfy query Q1.
In view of the foregoing example, it can be seen that the process represented by abstract syntax tree 10 adequately compares a data entry against the associated query in many situations. However, because of the construction of the abstract syntax tree, both branches were traversed before concluding that the data entry did not satisfy the query. It would have been sufficient to discover that the y parameter of data entry D1 did not satisfy the logic of query Q1 without having to consider the x parameter. Thus, the value of the x parameter was unnecessarily compared with query Q1 in the foregoing example.
Referring now abstract syntax tree 18 of FIG. 1B, comparison of data entry D1 against query Q2 involves a "greater than" operation according to node 19. As indicated by nodes 20 and 21, the process further involves comparing the x parameter of data entry D1 with the number 3. Thus, data entry D1 satisfies query Q2.
Comparison of data entry D1 with query Q3 is conducted, as shown by abstract syntax tree 22 of FIG. 1C, by executing a "not" operation depicted at node 23. The "not" operation yields a true value if the branch depending therefrom, which includes nodes 24-30 in this example, is false. The process advances to node 24, which indicates that the branch represents an "and" operation. Nodes 25, 26, and 27 represent an operation by which it is determined whether the y parameter of data entry D1 is greater than or equal to 5. In this example, the y parameter of data entry D1 has a value of 5, such that the branch of nodes 25-27 has a true value. The process steps back to node 24 and then advances to the branch including nodes 28, 29, and 30, which specify that the z parameter of data entry D1 is compared to the number 4 in a "greater than" operation. Because the z parameter has a value of 2, this branch is false. The process agrain steps back to node 24, which yields a false value. Stepping back to node 23, the "not" operation yields a true value, since the "and" operation of node 24 is false.
Abstract syntax trees 18 and 22 adequately compare data entries with the associated queries in many circumstances. However, the configuration of abstract syntax tree 22 required both the y and z parameters to be consecutively considered, whereas the value of the z parameter was sufficient to yield a true value for the abstract syntax tree. A significant disadvantage of the conventional processes for comparing data entries against arises when multiple queries are employed, such as those represented by FIGS. 1A-1C. For instance, queries Q1 and Q2 both relate to the value of an x parameter. When a data entry is processed using abstract syntax trees 10 and 18 of FIGS. 1A and 1B, the x parameter is considered twice. Likewise, the y parameter is separately considered in abstract syntax trees 10 and 22 of FIGS. 1A and 1C, respectively. Executing operations multiple times for the same parameter consumes significant computing resources, particularly when the number of separate query-based definitions is large One can imagine applications in which hundreds of queries or more are processed, resulting in repetitive or nearly repetitive operations on the same parameters.
In view of the foregoing, what is needed are methods for constructing and using filtering trees that combine the logical operations of multiple query-based definitions. Such filtering trees would be particularly advantageous if they could be capable of reducing, or eliminating the repetitive execution of operations on the same parameters that has been practiced using conventional techniques.